package algorithm.List.Queue;

/**
 * 用固定数组和双向链表实现双向队列
 * 双向队列是指可以从头尾两边加入或删除元素的队列
 */
public class MyDeque {
    public static class MyDequeWithList{
        //双向链表的思路是用头尾两个指针，可以自己设计双向链表，也可以用工具类

        //java提供的工具类已经是一个双向队列了，这里不再实现
    }
    public static class MyDequeWithArray{
        //固定数组的思路比较重要
        private int[] deque;
        private int size;
        private int limit;

        private int l,r;
        public MyDequeWithArray(int limit){
            deque=new int[limit];
            this.size=0;
            this.limit=limit;
            this.l=this.r=0;
        }

        /**
         * 从头部插入元素
         * 如果头部在0，l就跳到最右边
         * @param val
         * @return
         */
        public boolean insertFront(int val){
            if(isFull()) return false;
            else{
                if(isEmpty()){
                    l=r=0;
                    deque[0]=val;
                }else{
                    l=l==0?(limit-1):l-1;
                    deque[l]=val;
                }
                size++;
                return true;
            }
        }

        /**
         * 从尾部插入元素
         * 如果尾部在最右边，r就跳到最左边
         * @param val
         * @return
         */
        public boolean insertRear(int val){
            if(isFull()) return false;
            else{
                if(isEmpty()){
                    l=r=0;
                    deque[0]=val;
                }else{
                    r=r==limit-1?(0):r+1;
                    deque[r]=val;
                }
                size++;
                return true;
            }
        }

        /**
         * 删除元素的逻辑则比较简单
         * @return
         */
        public boolean popFront(){
            if(isEmpty()) return false;
            else{
                l=l==limit-1?0:l+1;
                size--;
                return true;
            }
        }

        public boolean popRear(){
            if(isEmpty()) return false;
            else{
                r=r==0?limit-1:r-1;
                size--;
                return true;
            }
        }


        public boolean isFull(){
            return size==limit;
        }
        public boolean isEmpty(){
            return size==0;
        }
    }
}
